package com.ljy.my_study.lintcode.线段树;

/**
 * @author James
 * @date 2018年4月12日
 */
public class SegmentTreeMain {
//	样例
//	对于数组 [0, 空，2, 3], 对应的线段树为：
//
//	                     [0, 3, count=3]
//	                     /             \
//	          [0,1,count=1]             [2,3,count=2]
//	          /         \               /            \
//	   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
//	query(1, 1), return 0
//
//	query(1, 2), return 1
//
//	query(2, 3), return 2
//
//	query(0, 2), return 2
	public static void main(String[] args) {
		Integer[] nums= {1,null,3,4};
		SegmentTreeNode node = build(nums,0, nums.length-1);
		System.out.println(node);
		System.out.println("---------------------");
		System.out.println(query2(node,0,1));
	}

	// 建立SegmentTreeNode
	public static SegmentTreeNode build(Integer[] nums,int start,int end) {
		if (start > end) {
			return null;
		}
		if (start == end) {
			return new SegmentTreeNode(start, end,nums[start]==null?0:1);
		}
		SegmentTreeNode node = new SegmentTreeNode(start, end);
		int leftNodeLeftIndex = start;
		int leftNodeRightIndex = (start + end) / 2;
		int rightNodeLeftIndex = (start + end) / 2 + 1;
		int rightNodeRightIndex = end;
//		node.left = build(leftNodeLeftIndex, leftNodeRightIndex);
//		node.right = build(rightNodeLeftIndex, rightNodeRightIndex);
		node.left = build(nums,leftNodeLeftIndex, leftNodeRightIndex);
		node.right = build(nums,rightNodeLeftIndex, rightNodeRightIndex);
		node.count=node.left.count+node.right.count;
		return node;
	}

	// 查询SegmentTreeNode
	public static int query(SegmentTreeNode node,int start,int end) {
		int result=doQuery(node,start,end);
		int nodeStartIndex = node.start;
		int nodeEndIndex = node.end;
		if(start==nodeStartIndex&&end==nodeEndIndex) {
			result--;
		}
		return result;
	}
	
	
	
	public static int doQuery(SegmentTreeNode node, int start, int end) {
		if(node==null) {
			return 0;
		}
		int nodeStartIndex = node.start;
		int nodeEndIndex = node.end;
		if (start > end) {
			return 0;
		}
		int result = 0;
		if (nodeStartIndex == nodeEndIndex) {
			if (start >= nodeStartIndex && end <= nodeEndIndex) {
				return node.count;
			}
		}else {
			if (start <= nodeStartIndex && end >= nodeEndIndex) {
				result+= 1;
			}
		}
		SegmentTreeNode leftNode = node.left;
		SegmentTreeNode rightNode = node.right;
		int midIndex = (nodeStartIndex + nodeEndIndex) / 2;
		
		if (start > midIndex) {
			result += doQuery(rightNode, start, end);
		} else if (end <= midIndex) {
			result += doQuery(leftNode, start, end);
		} else if (start <= midIndex && end >midIndex) {
			result += doQuery(leftNode, start, midIndex);
			result += doQuery(rightNode, midIndex+1, end);
		}
		return result;
	}
	
	public static int query2(SegmentTreeNode root, int start, int end) {  
        // write your code here  
        if(root == null){  
            return 0;  
        }  
        if(start > end){  
            return 0;  
        }  
        if(root.start >= start && root.end <= end){  
            return root.count;  
        }  
        if(root.start <= start && root.end >= end){  
            if(root.left != null && root.right != null){  
                return query(root.left , Math.max(start,root.left.start) , Math.min(root.left.end , end))+query(root.right , Math.max(start ,root.right.start) , Math.min(end , root.right.end));  
            }else if(root.left != null){  
                return query(root.left , Math.max(start,root.left.start) , Math.min(root.left.end , end));  
            }else if(root.right != null){  
                return query(root.right , Math.max(start ,root.right.start) , Math.min(end , root.right.end));  
            }else{  
                return 0;  
            }  
        }  
        if(root.start >= start && root.start <=end && root.end >end){  
            return query(root , root.start , end);  
        }  
        if(root.end >= start && root.end <= end && root.end > start){  
            return query(root , start , root.end);  
        }  
        return 0;  
    }  
}
